---
title: 集合
description: Java 集合类库是用来持有对象的。从设计上讲，它可以分为两个不同的概念，表示为类库库的两个基本接口,Collection 和 Map。
---

## 基本概念

Java 集合类库是用来持有对象的。从设计上讲，它可以分为两个不同的概念，表示为类库库的两个基本接口。

1. Collection : 一个由单独元素组成的序列，而且这些元素要符合一条或多条规则。List 必须按照元素插入的顺序去保存它们；Set 中能保存重复元素；而 Queue 则要按照排队规则来输出元素（和插入元素的顺序相同）。

2. Map : 一组键值对象对，使用键来查找值。ArrayList 使用一个数值来查找某个对象，所以在某种意义上它将数值和其他对象关联在了一起；而 Map 使用另一个对象来查找某个对象，它也被称为关联数组，因为它将对象和对象关联在了一起。

**序列**是持有一组对象的一种方式，而 Collection 接口就是序列概念的一般化。

```java title='一个简单的示例：填充一个保存 Integer 对象的 Collection ，然后打印生成的集合中的每一个元素。'
public class SimpleCollection {
    public static void main(String[] args) {
        Collection<Integer> c = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            //自动装箱
            c.add(i);
        }
        for (Integer i : c) {
            System.out.print(i + " ,");
        }
    }
}
```

顾名思义，add() 方法是要将一个元素放入 Collection 中，所有的 Collection 都可以使用 for-in 语法遍历。

## 添加元素

java.util 中的 Arrays 和 Collections 类都包含了一些工具方法，用于向一个 Collection 中添加一组元素。

Arrays.asList() 方法可以接受一个数组，或者或者一个用逗号分隔的元素列表（使用可变参数）并将其转换为一个 List 对象。

Collections.addAll() 方法接受一个 Collection 对象、一个数组，或者一个用逗号分割的列表，将其中所有的元素都添加到这个 Collection 中。

```java title='向 Collection 对象中添加一组元素'
public class AddingGroups {
    public static void main(String[] args) {
        Collection<Integer> collection = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));
        Integer[] moreInts = {6, 7, 8, 9, 10};
        collection.addAll(Arrays.asList(moreInts));

        Collections.addAll(collection, 11, 12, 13, 14, 15);
        Collections.addAll(collection, moreInts);
        //生成一个底层为数组的列表
        List<Integer> list = Arrays.asList(16, 17, 18, 19, 20);
        Arrays.asList(new int[]{1, 2, 3});
        list.set(1, 99);
        list.add(21);//运行时错误，底层的数组大小不能改变。
    }
}
```

Collection 的构造器可以接受另一个 Collection ，用于对自己进行初始化，因此可以使用 Arrays.asList() 来生成该构造器的输入。推荐使用空的 Collection，之后使用 Collections.addAll() 这种方式。

Collection.addAll() 方法只能接受另一个 Collection 对象作为参数，所以不如 Arrays.asList() 或 Collections.addAll() 灵活，因为这两种方式提供了可变的参数列表。

也可以直接使用 Arrays.asList 的输出，将其当为一个 List ，但是其底层实现是数组，大小无法调整。如果添加或删除元素，这些操作会尝试改变数组的大小，所以会出现 `Unsupported Operation`运行时错误。

```java
class Snow { }

class Power extends Snow { }
class Light extends Power{ }
class Heavy extends Power {}
class Crusty extends Snow {}
class Slush extends Snow {}

public class AsListInference {
    public static void main(String[] args) {
        List<Snow> snow1 = Arrays.asList(new Crusty(), new Slush(), new Power());
//        snow1.add(new Heavy());//异常

        List<Snow> snow2 = Arrays.asList(new Light(), new Heavy());
//        snow2.add(new Heavy());

        List<Snow> snow3 = new ArrayList<>();
        Collections.addAll(snow3, new Light(), new Heavy(), new Power());
        snow3.add(new Crusty());

        //以显式类型参数说明作为提示
        List<Snow> snow4 = Arrays.<Snow>asList(new Light(), new Heavy(), new Slush());
//        snow4.add(new Power());
    }
}
```

## 打印集合

```java
public class PrintingCollections {
    static Collection fill(Collection<String> collection) {
        collection.add("rat");
        collection.add("cat");
        collection.add("dog");
        collection.add("dog");
        return collection;
    }

    static Map fill(Map<String, String> map) {
        map.put("rat", "Fuzzy");
        map.put("cat", "Rags");
        map.put("dog", "Bosco");
        map.put("dog", "Spot");
        return map;
    }

    public static void main(String[] args) {
        System.out.println(fill(new ArrayList<>()));
        System.out.println(fill(new LinkedList<>()));
        System.out.println(fill(new HashSet<>()));
        System.out.println(fill(new TreeSet<>()));
        System.out.println(fill(new LinkedHashSet<>()));
        System.out.println(fill(new HashMap<>()));
        System.out.println(fill(new TreeMap<>()));
        System.out.println(fill(new LinkedHashMap<>()));
    }
}
```

Java 集合类库有两种主要类型。其区别在于集合中的每个“槽”（slot）内持有的条目数。Collection 在每个槽内只能保存一个条目，包括：

- List，以指定顺序保存一组条目；
- Set,同样的条目只能存入一个；
- Queue, 只能在集合的一端插入对象，而在另一端移除对象；

Map 在每个槽内持有两个对象，即**键**和与之关联的**值**。

ArrayList 和 LinkedList 都是 List 类型，它们都是以插入顺序保存元素的。两者的不同之处不仅是对于特定类型的操作在性能上有差别，而且 LinkedList 包含的操作也多于 ArrayList。

HashSet、TreeSet 和 LinkedHashSet 都是 Set 类型。对于相同的条目， Set 只会保存一个，而且不同的 Set 实现会以不同的方式存储元素。
HashSet 使用了一个相当复杂的方式存储元素，可以很快的检索出元素，但不保证存储顺序，如果存储顺序非常重要，可以使用 TreeSet
它会以升序保存对象；或使用 LinkedHashSet，它会按照添加顺序来保存元素。

Map（也称为关联数组）使用键来查找对象，就像一个简单的数据库。被关联的对象被称为值。就像使用数组索引一样。正是因为这样，对于相同的键，Map 只能存储一个。

Map.put(key,value) 的作用是添加一个值(value),并将其与一个 key 关联起来。Map.get(key) 会得到与这个键(key)关联的值。

键和值在 HashMap 之中的保存顺序不同于插入顺序，这是因为 HashMap 使用了一种非常快速的算法，而该算法会控制顺序。TreeMap 会按照键的升序来排序，LinkedHashMap 则会按照插入顺序来保存键，同时保留了 HashMap 的查找速度。

## List

List 接口在 Collection 的基础上增加了一些方法，支持在 List 中间插入和移除元素。List 会以特定的顺序维护元素。
有两种类型的 List 。

- 基本的 ArrayList，擅长随机访问元素，但是在 List 的中间插入或删除元素比较慢。
* LinkedList ，提供了理想的顺序访问性能，在 List 的中间插入或删除元素的成本都比较低。LinkedList 随机访问性能相对较差，但是与 ArrayList 相比提供了更多功能。


可以使用 contains() 方法来确定某个对象是否在该列表中。要移除一个对象，可以将该对象的引用传给 remove() 方法。此外，指向某个对象的引用，也可以使用 indexOf() 方法获得该对象在 List 中的索引编号。

当确定某个元素是否在 List 中，查找某个元素的索引编号，以及按照引用从 List 中删除某个元素时,都会用到 equals 方法。List 的行为会随着 equals 行为的改变而改变。

subList 方法可以创建一个较大列表的一个片段，将其再传给较大列表的 containsAll 方法，结果自然是 true。subList 生成的列表，其底层还是原始列表。

retainAll 方法实际上是求交集的操作，它产生的行为依赖于 equals 方法。

remove 方法也支持传入索引移除某个元素，这样比通过对象引用来移除更为明确，因为使用索引时不用担心 equals 方法的行为。

removaAll 方法的运行也是基于 equals 方法的。顾名思意，它会从列表中删除参数 List 中包含的所有对象。

set 用于设置值。

List 有一个重载的 addAll 方法，可以将一个新列表插入原始列表的中间，而不是只能 Collection 中 addAll 方法将其追加到原始列表末尾。

## Iterator

迭代器是一种设计模式。迭代器是一个对象，它可以在序列中移动，并且用来选择该序列中的每个对象，而使用它的程序员不用知道和关心序列的底层结构。此外，迭代器通常是所谓的轻量级对象，创建的成本很低，所以会有一些限制，比如 Java 的Iterator 只能向一个方向移动。

迭代器只能做如下几件事：

* 使用 iterator() 方法让 Collection 返回一个 Iterator。这个迭代器将准备好返回序列中的第一个元素。
* 使用 next 方法获得序列中的下一个对象。
* 使用 hasNext 方法检查序列中是否还有更多对象。
* 使用 remove 方法删除该迭代器最近返回的元素。

有了 Iterator 就不用再为集合中元素的数量操心了，hasNext() 和 next() 会为我们处理。

如果只是在 List 中向前遍历，不打算修改 List 对象本身，for-in 语法更简洁。

Iterator 也可以删除由 next 产生的最后一个元素，这意味着在调用 remove 之气那必须调用 next 。**迭代器统一了对集合的访问。**

## LinkedList
和 ArrayList 一样，LinkedList 实现了基本的 List 的接口。但是与 ArrayList 相比，它们在 List 中间执行插入和删除操作的效率更高，不过随机访问操作的表现要差一些。


## Set
Set 中不允许出现重复的对象值，对于等价对象的实例，如果尝试添加多个，那么 Set 会阻止。

Set 与 Collection 有相同的接口，所以不像 List 的两种类型那样有额外的功能。相反，Set 就是一个 Collection，只是行为不同（这就是继承和多态的理想使用场景：表现不同的行为）。Set 根据对象的值来确定成员身份。
```java title='示例代码使用了一个持有 Integer 对象的 HashSet'
public class SetOfInteger {
    public static void main(String[] args) {
        Random random = new Random(47);
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < 10000; i++) {
            set.add(random.nextInt(30));
        }
        System.out.println("set = " + set);
        //set = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]
    }
}
```
生成了 10000 个 0~29 范围内的数，并将其添加到 Set 中，所以不难想象，每个值都会重复很多次。然而，每个值都只有一个实例出现在了结果中。

TreeSet 将元素存储在红黑树数据结构中，而 HashSet 使用的是哈希函数。LinkedHashSet 也使用哈希来提升查询效率，但它是使用链表按照插入顺序来维护元素的。
显然，现在的 JDK 版本，哈希算法变了。但是不应该依赖于这种行为。

```java title='这里 HashSet 就没有排序'
public class SetOfString {
    public static void main(String[] args) {
        Set<String> colors = new HashSet<>();
        for (int i = 0; i < 100; i++) {
            colors.add("Yellow");
            colors.add("Blue");
            colors.add("Red");
            colors.add("Red");
            colors.add("Orange");
            colors.add("Yellow");
            colors.add("Blue");
            colors.add("Purple");
        }
        System.out.println("colors = " + colors);
        //colors = [Red, Yellow, Blue, Purple, Orange]
    }
}
```
如果要给输出结果排序，一种方法是使用 TreeSet 来代替 HashSet ：

```java
public class SortedSetOfString {
    public static void main(String[] args) {
        Set<String> colors = new TreeSet<>();
        for (int i = 0; i < 100; i++) {
            colors.add("Yellow");
            colors.add("Blue");
            colors.add("Red");
            colors.add("Red");
            colors.add("Orange");
            colors.add("Yellow");
            colors.add("Blue");
            colors.add("Purple");
        }
        System.out.println("colors = " + colors);
        //colors = [Blue, Orange, Purple, Red, Yellow]
    }
}
```
最常见的操作之一就是使用 contains 来测试 Set 成员是否存在。
## Queue
队列（queue）是一个典型的先进先出（FIFO）的集合。队列常用来将对象从程序的一个区域可靠地转移到另一个区域。队列在并发编程中十分重要，因为它们可以安全地将对象从一个任务转移到另一个任务。

LinkedList 实现了 Queue 接口，提供了支持队列行为的方法，因此 LinkedList 可以作为 Queue 的一种实现来使用。通过将LinkedList 向上转型为 Queue。

```java
package pub.wkq.collections.queue;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Random;

public class QueueDemo {
    public static void printQ(Queue queue) {
        while (queue.peek() != null) {
            System.out.print(queue.remove() + " ");
        }
        System.out.println();
    }

    /**
     * 8 1 1 1 5 14 3 1 0 1
     * B r o n t o s a u r u s
     * @param args
     */
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        Random random = new Random(47);
        for (int i = 0; i < 10; i++) {
            queue.offer(random.nextInt(i + 10));
        }
        printQ(queue);
        Queue<Character> qc = new LinkedList<>();
        for (char c : "Brontosaurus".toCharArray()) {
            qc.offer(c);
        }
        printQ(qc);
    }
}
```
offer() 是 Queue 特有的方法之一，负责在队列尾部插入一个元素，如果无法插入则返回 false。peek() 和 element() 都会返回队列的头部元素，不回将其从队列中删除，但是如果队列为空，peek() 会返回 null，element() 会抛出 NoSuchElementException 。poll() 和 remove() 会将头部元素从队列中删除，然后返回。但是如果队列为空， poll() 会返回 null，而 remove() 会抛出 NoSuchElementException.


Queue 特有的方法提供了完整且独立的注解。
